package com.wwz.leetcode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode18 {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> resList = new ArrayList<>();
        int length = nums.length;
        if (length < 4) {
            return resList;

        }
        // 排序
        Arrays.sort(nums);
        for (int first = 0; first < length - 3; first++) {

            // 不能再有和第一位相同的了 不然会重复
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < length - 2; second++) {

                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                for (int third = second + 1; third < length - 1; third++) {
                    // 需要和上一次枚举的数不相同
                    if (third > second + 1 && nums[third] == nums[third - 1]) {
                        continue;
                    }
                    int four = third + 1;
                    while (four < length && !(Long.valueOf(nums[first] + nums[second] + nums[third] + nums[four]).equals(Long.valueOf(target)))) {
                        four++;
                    }
                    Double v = null;
                    if (four < length){
                         v = Long.valueOf(nums[first]).doubleValue() + Long.valueOf(nums[second]).doubleValue()
                                + Long.valueOf(nums[third]).doubleValue() + Long.valueOf(nums[four]).doubleValue();
                    }

                    if (four < length && v.doubleValue() ==Long.valueOf(target)) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        list.add(nums[four]);
                        resList.add(list);
                    }
                }

            }
        }
        return resList;
    }


    @Test
    public void test() {
//        System.out.println(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
////        输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
        System.out.println(fourSum(new int[]{2, 2, 2, 2}, 8));
//        System.out.println(fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296));


    }
}
